package com.cong.sort.merge;

import java.util.Arrays;

/**
 * 归并排序
 *
 * @author cong
 * <p>
 * created on 2021/3/19 下午2:10
 */
public class MergeSort {

    public static void main(String[] args) {
        int[] arr = {1, 4, 7, 8, 3, 6, 9};
        sort(arr, 0, arr.length-1);
        print(arr);
    }

    public static void sort(int[] arr, int left, int right) {
        if (left == right) return;
        //计算中间值
        int mid = left + (right - left) / 2;
        //递归排序左半边
        sort(arr, left, mid);
        //排序右半边
        sort(arr, mid + 1, right);
        //归并
        merge(arr, left, mid + 1, right);

    }

    private static void merge(int[] arr, int left, int right, int rightBound) {
        int mid = right - 1;
        int[] temp = new int[rightBound - left + 1];
        int i = left;//前半段初始位置
        int j = right;//后半段初始位置
        int k = 0;//临时数组下标
        while (i <= mid && j <= rightBound) {
            temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
        }
        //前半部分有剩余，直接复制剩下的数组
        while (i <= mid) temp[k++] = arr[i++];
        //后半部分是否有剩余部分
        while (j <= rightBound) temp[k++] = arr[j++];
        for (int l = 0; l < temp.length; l++) {
            arr[left + l] = temp[l];
        }

    }

    private static void merge2(int[] arr) {
        int mid = arr.length >> 1;
        System.out.println(mid);
        int[] temp = new int[arr.length];
        int i = 0;//前半段初始位置
        int j = mid + 1;//后半段初始位置
        int k = 0;//临时数组下标
        while (i < mid && j < arr.length) {
            temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
//            if (arr[i] <= arr[j]) {
//                temp[k++] = arr[i++];
//                //i++;
//                //k++;
//            } else {
//                temp[k++] = arr[j++];
//                //下一个位置
//                //j++;
//                //k++;
//            }
        }
        //前半部分有剩余，直接复制剩下的数组
        while (i < mid) temp[k++] = arr[i++];
        //后半部分是否有剩余部分
        while (j < arr.length) temp[k++] = arr[j++];
        print(temp);

    }

    static void swap(int[] arr, int source, int target) {
        int temp = arr[target];
        arr[target] = arr[source];
        arr[source] = temp;
    }

    static void print(int[] arr) {
        System.out.print(Arrays.toString(arr));

    }
}
